package main.Q101_200;

import java.util.*;

public class Q111_120 {
    public static void main(String[] args) {
        System.out.println("Question111：二叉树的最小深度");
        System.out.println("Question112：路径总和");
        System.out.println("Question113：路径总和Ⅱ");
        System.out.println("Question114：二叉树展开为链表");
        System.out.println("Question115：");
        System.out.println("Question116：填充每个节点的下一个右侧节点指针");
        System.out.println("Question117：填充每个节点的下一个右侧节点指针Ⅱ");
        System.out.println("Question118：杨辉三角");
        System.out.println("Question119：杨辉三角Ⅱ");
        System.out.println("Question120：三角形最小路径和");
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

class Question111{
    public int minDepth(TreeNode root) {
        int result=0;
        if (process(root)==null) return result;
        result=process(root).intValue();
        return result;
    }
    public Integer process(TreeNode root){
        if (root==null) return null;
        Integer leftHeight=process(root.left);
        Integer rightHeight=process(root.right);
        if (leftHeight==null&&rightHeight==null) return 1;
        if (rightHeight==null&&leftHeight!=null) return leftHeight+1;
        if (leftHeight==null&&rightHeight!=null) return rightHeight+1;
        return Math.min(leftHeight,rightHeight)+1;
    }
}

class Question112{
    public boolean process(TreeNode root,int curSum){
        if (root==null) return false;
        curSum-=root.val;
        if (root.left==null&&root.right==null&&curSum==0) return true;
        boolean left=process(root.left,curSum);
        boolean right=process(root.right,curSum);
        return left==true ? left : right;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return process(root,targetSum);
    }
}

class Question113{
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        peocess(root, targetSum);
        return ret;
    }

    public void peocess(TreeNode root, int targetSum) {
        if (root == null) return;
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        peocess(root.left, targetSum);
        peocess(root.right, targetSum);
        path.pollLast();
    }
}

class Question114{
    public void preOrder(TreeNode root,ArrayList<TreeNode> list){
        if (root==null) return;
        list.add(root);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> nodeList=new ArrayList<>();
        preOrder(root,nodeList);
        if (nodeList.size()>0) {
            TreeNode curNode = nodeList.get(0);
            for (int i = 1; i < nodeList.size(); i++) {
                TreeNode temp = nodeList.get(i);
                curNode.left = null;
                curNode.right = temp;
                curNode = temp;
            }
        }
    }
}

class Question116{
    public Node connect(Node root) {
        if (root==null||root.left==null) return root;
        Queue<Node> queue=new LinkedList<>();
        HashMap<Node,Integer> map=new HashMap<>();
        queue.add(root);
        int curCol=1;//当前遍历的层数
        map.put(root,1);
        while (!queue.isEmpty()){
            Node curNode=queue.poll();//出栈
            if (queue.isEmpty()){//当前元素为该层最右侧元素
                curNode.next=null;
                curCol++;
            }else {//当前元素不为该层最右侧元素
                Node temp=queue.peek();
                if (map.get(temp)!=curCol){
                    curNode.next=null;
                    curCol++;
                }else curNode.next=temp;
            }
            if (curNode.left!=null) {//下一层元素入栈
                queue.add(curNode.left);
                map.put(curNode.left,map.get(curNode)+1);//记录该节点所在层
            }
            if (curNode.right!=null) {
                queue.add(curNode.right);
                map.put(curNode.right,map.get(curNode)+1);
            }
        }
        return root;
    }
}

class Question117{
    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //每一层的数量
            int levelCount = queue.size();
            //前一个节点
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {//一层的节点全部入队后，再将该层节点全部出队
                //出队
                Node node = queue.poll();
                //如果pre为空就表示node节点是这一行的第一个，
                //没有前一个节点指向他，否则就让前一个节点指向他
                if (pre != null) {
                    pre.next = node;
                }
                //然后再让当前节点成为前一个节点
                pre = node;
                //左右子节点如果不为空就入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }
}

class Question118{
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result=new ArrayList<>();
        for (int i=0;i<numRows;i++){
            List<Integer> row=new ArrayList<>();
            row.add(1);//添加第一个元素
            for (int j=1;j<i;j++){//添加中间元素
                row.add(result.get(i-1).get(j-1)+result.get(i-1).get(j));
            }
            if (i!=0) row.add(1);//添加最后一个元素
            result.add(row);
        }
        return result;
    }
}

class Question119{
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> result=new ArrayList<>();
        for (int i=0;i<rowIndex+1;i++){
            List<Integer> row=new ArrayList<>();
            row.add(1);//添加第一个元素
            for (int j=1;j<i;j++){//添加中间元素
                row.add(result.get(i-1).get(j-1)+result.get(i-1).get(j));
            }
            if (i!=0) row.add(1);//添加最后一个元素
            result.add(row);
        }
        return result.get(rowIndex);
    }
}

class Question120{
    public int minimumTotal(List<List<Integer>> triangle) {
        int col=triangle.get(triangle.size()-1).size(),row= triangle.size();
        int[][] dp=new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<i+1;j++){
                if (j==0&&i==0) dp[i][j]=triangle.get(i).get(j);//0行0列元素
                else if (j==0&&i!=0) dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);//0列元素
                else {
                    if (j<i) {
                        dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
                    }else {
                        dp[i][j]=triangle.get(i).get(j)+dp[i - 1][j - 1];
                    }
                }
            }
        }
        int min=dp[row-1][0];
        for (int i=0;i<col;i++){
            if (dp[row-1][i]<min) min=dp[row-1][i];
        }
        return min;
    }
}